题解 P2890@洛谷 【[USACO07OPEN]Cheapest Palindrome G】

小清新 dp 题喜加一。

题意：我们有一个字符串 $s$，长度为 $m$。我们可以在任意位置添加或删除一个字母，共有 $n$ 个字母可供选择，添加或删除不同字母所需花费不同，求使这个字符串为回文串的最少花费。

显然区间 dp，设计状态 $dp_{i,j}$ 表示使 $s_i\sim s_j$ 为回文串所需的最少花费。

下面考虑状态转移：

我们枚举区间长度 $l\in\left[0,m\right)$，然后枚举左端点 $i$，得到右端点 $j$。

对于一个回文字符串，在它的左侧加一个字符后要想保持回文性，有两种方法：在右侧添加一个同样的字符，或者将左侧字符删去。可以看出，对于一个字符而言，插入和删除的权值没有区别，可以只存最小值。

考虑这个字符串，我们可以看做它是由回文串在左侧添加一个字符得到的，也可以看做它是在右侧添加一个字符得到的。我们选择这两者的更小的那个即可：（$mp$ 表示对于一个字符，插入和删除的权值中小的那个）

$dp_{i,j}=\min(dp_{i+1,j}+mp_{s_i},dp_{i,j-1}+mp_{s_j})$

当然，有一种情况较为特殊：$s_i=s_j$，此时我们需要特判。如果 $l\le 1$，则该串本身回文， $dp_{i,j}=0$。否则，$dp_{i,j}=\min(dp_{i,j},dp_{i+1,j-1})$。

于是，我们便得到了本题的三个方程。

代码：

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int M = 2005;

int n, m;
string s;
map<char, int> mp;
int dp[M][M];

int main() {
	scanf("%d%d", &n, &m);
	cin>>s;
	memset(dp, 0x3f, sizeof(dp));
	for(int i=0;i<m;i++) {
		for(int j=0;j<=i;j++) dp[i][j] = 0;
	}
	for(int i=1;i<=n;i++) {
		char c = getchar();
		for(;c==' '||c=='\n';c=getchar());
		int a, b;
		scanf("%d%d", &a, &b);
		mp[c] = min(a, b);
	}
	for(int l=0;l<m;l++) {
		for(int i=0,j=l;j<m;i++,j++) {
			dp[i][j] = min(dp[i+1][j]+mp[s[i]], dp[i][j-1]+mp[s[j]]);
			if(s[i] == s[j]) dp[i][j] = min(dp[i][j], (l <= 1 ? 0 : dp[i+1][j-1]));
		}
	}
	printf("%d\n", dp[0][m-1]);
	return 0;
}